{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Non-Zero Product of the Array Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minNonZeroProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组元素的最小非零乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>p</code>&nbsp;。你有一个下标从 <strong>1</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，这个数组包含范围&nbsp;<code>[1, 2<sup>p</sup> - 1]</code>&nbsp;内所有整数的二进制形式（两端都 <strong>包含</strong>）。你可以进行以下操作 <strong>任意</strong>&nbsp;次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从 <code>nums</code>&nbsp;中选择两个元素&nbsp;<code>x</code>&nbsp;和&nbsp;<code>y</code>&nbsp; 。</li>\n",
    "\t<li>选择 <code>x</code>&nbsp;中的一位与 <code>y</code>&nbsp;对应位置的位交换。对应位置指的是两个整数 <strong>相同位置</strong>&nbsp;的二进制位。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，如果&nbsp;<code>x = 11<em><strong>0</strong></em>1</code>&nbsp;且&nbsp;<code>y = 00<em><strong>1</strong></em>1</code>&nbsp;，交换右边数起第 <code>2</code>&nbsp;位后，我们得到&nbsp;<code>x = 11<em><strong>1</strong></em>1</code> 和&nbsp;<code>y = 00<em><strong>0</strong></em>1</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你算出进行以上操作 <strong>任意次</strong>&nbsp;以后，<code>nums</code>&nbsp;能得到的 <strong>最小非零</strong>&nbsp;乘积。将乘积对<em>&nbsp;</em><code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p><strong>注意：</strong>答案应为取余 <strong>之前</strong>&nbsp;的最小值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>p = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>nums = [1] 。\n",
    "只有一个元素，所以乘积为该元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>p = 2\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>nums = [01, 10, 11] 。\n",
    "所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。\n",
    "所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>p = 3\n",
    "<b>输出：</b>1512\n",
    "<b>解释：</b>nums = [001, 010, 011, 100, 101, 110, 111]\n",
    "- 第一次操作中，我们交换第二个和第五个元素最左边的数位。\n",
    "    - 结果数组为 [001, <em><strong>1</strong></em>10, 011, 100, <em><strong>0</strong></em>01, 110, 111] 。\n",
    "- 第二次操作中，我们交换第三个和第四个元素中间的数位。\n",
    "    - 结果数组为 [001, 110, 0<em><strong>0</strong></em>1, 1<em><strong>1</strong></em>0, 001, 110, 111] 。\n",
    "数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= p &lt;= 60</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-non-zero-product-of-the-array-elements](https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-non-zero-product-of-the-array-elements](https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minNonZeroProduct(self, p: int) -> int:\n",
    "\t\t# (2^p−1)⋅(2^p−2)^(2^p−1−1)\n",
    "\t\t# return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n",
    "\n",
    "\t\tans = [0, 1, 6, 1512, 581202553, 202795991, 57405498, 316555604, 9253531, 857438053, 586669277, 647824153,\n",
    "\t\t       93512543,\n",
    "\t\t       391630296, 187678728, 431467833, 539112180, 368376380, 150112795, 484576688, 212293935, 828477683,\n",
    "\t\t       106294648,\n",
    "\t\t       618323081, 186692306, 513022074, 109245444, 821184946, 2043018, 26450314, 945196305, 138191773,\n",
    "\t\t       505517599,\n",
    "\t\t       861896614, 640964173, 112322054, 217659727, 680742062, 673217940, 945471045, 554966674, 190830260,\n",
    "\t\t       403329489,\n",
    "\t\t       305023508, 229675479, 865308368, 689473871, 161536946, 99452142, 720364340, 172386396, 198445540,\n",
    "\t\t       265347860,\n",
    "\t\t       504260931, 247773741, 65332879, 891336224, 221172799, 643213635, 926891661, 813987236]\n",
    "\t\treturn ans[p]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minNonZeroProduct(self, p: int) -> int:\n",
    "\t\t# (2^p−1)⋅(2^p−2)^(2^p−1−1)\n",
    "\t\treturn (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        limit = pow(2,p) - 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        return limit * pow(limit - 1,limit // 2,mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        x = 1 << (p - 1)\n",
    "        a = (2 * x - 2) % M\n",
    "        k = x - 1\n",
    "        ret = 1\n",
    "        while k > 0:\n",
    "            if k & 1:\n",
    "                ret = (ret * a) % M\n",
    "            k >>= 1\n",
    "            a = a * a % M\n",
    "        # print(x, ret)\n",
    "        return (2 * x - 1) * ret % M "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        r = (1 << p) - 1\n",
    "        res = r ^ 1\n",
    "        w = (r // 2).bit_length()\n",
    "        ans = 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        while w:\n",
    "            w -= 1\n",
    "            ans = (ans * res) % MOD\n",
    "            res = (res * res) % MOD\n",
    "\n",
    "        return (ans * r) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (pow(2**p-2,2**(p-1)-1,10**9+7)*(2**p-1))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        r = (1 << p) - 1 - (1 << (p - 1))\n",
    "        return pow((1 << p) - 1, 1) * pow((1 << p) - 2, (1 << (p - 1)) - 1, 10**9+7) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        x = pow(2, p)\n",
    "        return (x - 1) * pow((x - 2), x // 2 - 1, mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        def myPow(x, n):\n",
    "            ans = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    ans = (ans * x) % MOD\n",
    "                x = x * x % MOD\n",
    "                n //= 2\n",
    "            return ans\n",
    "\n",
    "        if p == 1:  return 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = myPow(((1 << p) - 2), (((1 << p) - 2) // 2)) \n",
    "        return (ans * ((1 << p) - 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        x = self.quickPow(2, p, mod)\n",
    "        res1 = x - 1\n",
    "        if res1 < 0:\n",
    "            res1 += mod\n",
    "        \n",
    "        e = self.quickPow(2, p - 1, mod - 1)\n",
    "        e -= 1\n",
    "        if e < 0:\n",
    "            e += mod - 1\n",
    "        \n",
    "        x -= 2\n",
    "        if x < 0:\n",
    "            x += mod\n",
    "        res2 = self.quickPow(x, e, mod)\n",
    "\n",
    "        return res1 * res2 % mod\n",
    "    \n",
    "    def quickPow(self, base, p, mod):\n",
    "        if p == 0:\n",
    "            return 1\n",
    "        elif p == 1:\n",
    "            return base\n",
    "        \n",
    "        res = self.quickPow(base, p // 2, mod)\n",
    "        res = res * res % mod\n",
    "        if p % 2 == 1:\n",
    "            res = res * base % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2**p-1)*pow(2**p-2,2**(p-1)-1,10**9+7)%(10**9+7) if p>1 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        # 1 <= p <= 60 ;;  已经是一个巨大的数了\n",
    "        # 应该是对称的\n",
    "        # 总共有2^p-1个数   一个是2^p-1, 剩下一半是2^p-2\n",
    "        mod = 10 ** 9 + 7\n",
    "        x = 2**p-1\n",
    "        n = (2**p-2) // 2\n",
    "        return (x * pow(x-1, n, mod)) % mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        # 每一位都有 n = 2 ^ (p - 1) 个 1 和 n - 1 个 0\n",
    "        # 考虑贪心做法,构成 n - 1 个 1, n - 1 个 (2 ^ p - 2), 1 个 (2 ^ p - 1)\n",
    "        # 证明这是最小的, 任意的执行交换都会使得最小非零乘积变大\n",
    "        # 考虑两种交换方式, 1 & (6 | 7) 之间进行某些位置上的 1 交换, 6 & 7 的交换无意义\n",
    "        # Δ = -a ^ 2 + (x - 1)a = -(a - (x - 1) / 2) ^ 2 + (x - 1) ^ 2 / 4 > 0\n",
    "        # 矩阵快速幂计算取模\n",
    "        mod = int(10**9 + 7)\n",
    "        if p == 1:\n",
    "            return 1\n",
    "        n = 1 << p\n",
    "        def quick_power(base, power):\n",
    "            ans = 1\n",
    "            while power:\n",
    "                if power & 1:\n",
    "                    ans = ans * base % mod\n",
    "                base = base * base % mod\n",
    "                power >>= 1\n",
    "            return ans\n",
    "        return quick_power(n - 2, (n >> 1) - 1) * (n - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        module = 10**9+7\n",
    "        x = 2**p - 1\n",
    "        x1 = x // 2\n",
    "        ans = pow(x-1, x1, module)\n",
    "        ans *= x\n",
    "        ans %= module\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        max_num = pow(2, p, MOD) - 1\n",
    "        \n",
    "        x = max_num - 1\n",
    "        time = pow(2, p - 1) - 1\n",
    "\n",
    "        res = max_num % MOD * pow(x, time, MOD) % MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 1\n",
    "        mask = (1 << p) - 1\n",
    "        ans *= mask\n",
    "        m = 2 ** (p - 1) - 1\n",
    "        mask = mask & (mask - 1)\n",
    "        ans *= pow(mask, m, MOD)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        def myPow(x, n):\n",
    "            ans = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    ans = (ans * x) % MOD\n",
    "                x = x * x % MOD\n",
    "                n //= 2\n",
    "            return ans\n",
    "\n",
    "        if p == 1:  return 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = myPow(((1 << p) - 2), (((1 << p) - 2) // 2)) \n",
    "        return (ans * ((1 << p) - 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        max_num = pow(2, p, MOD) - 1\n",
    "        \n",
    "        x = max_num - 1\n",
    "        time = pow(2, p - 1) - 1\n",
    "\n",
    "        res = max_num % MOD * pow(x, time, MOD) % MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        # 每一位都有 n = 2 ^ (p - 1) 个 1 和 n - 1 个 0\n",
    "        # 考虑贪心做法,构成 n - 1 个 1, n - 1 个 (2 ^ p - 2), 1 个 (2 ^ p - 1)\n",
    "        # 证明这是最小的, 任意的执行交换都会使得最小非零乘积变大\n",
    "        # 考虑两种交换方式, 1 & (6 | 7) 之间进行某些位置上的 1 交换, 6 & 7 的交换无意义\n",
    "        # Δ = -a ^ 2 + (x - 1)a = -(a - (x - 1) / 2) ^ 2 + (x - 1) ^ 2 / 4 > 0\n",
    "        # 矩阵快速幂计算取模\n",
    "        mod = int(10**9 + 7)\n",
    "        if p == 1:\n",
    "            return 1\n",
    "        n = 1 << p\n",
    "        def quick_power(base, power):\n",
    "            ans = 1\n",
    "            while power:\n",
    "                if power & 1:\n",
    "                    ans = ans * base % mod\n",
    "                base = base * base % mod\n",
    "                power >>= 1\n",
    "            return ans\n",
    "        return quick_power(n - 2, (n >> 1) - 1) * (n - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        \n",
    "        t = (1 << p) - 1\n",
    "        q = (t - 1) // 2\n",
    "        return pow(t - 1, q, kmod) * t % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        max_val = 2 ** p - 1  # 最大整数\n",
    "        min_val = 1  # 最小整数\n",
    "\n",
    "        # 计算 (x ** y) % MOD\n",
    "        def power(x: int, y: int, MOD: int) -> int:\n",
    "            result = 1\n",
    "            x %= MOD\n",
    "            while y > 0:\n",
    "                if y % 2:  # 如果 y 是奇数\n",
    "                    result = (result * x) % MOD\n",
    "                y //= 2\n",
    "                x = (x * x) % MOD\n",
    "            return result\n",
    "\n",
    "        # 最小乘积\n",
    "        return (power(min_val, (2 ** (p - 1) - 1), MOD) * \n",
    "                power(max_val - 1, 2 ** (p - 1) - 1, MOD) * \n",
    "                max_val) % MOD\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.minNonZeroProduct(1))  # 输出应为 1\n",
    "print(sol.minNonZeroProduct(2))  # 输出应为 6\n",
    "print(sol.minNonZeroProduct(3))  # 输出应为 1512\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        ans = pow(2**p-2, 2**(p-1)-1, mod)*(2**p-1)\n",
    " \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        if p<=1:\n",
    "            # 只有一个数字，无需替换\n",
    "            return 1 \n",
    "        # 每当p增加1\n",
    "        # 在最高位，即第p位，增加了 2**(p-1) 个1\n",
    "        # 其他位置，增加了 2**(p-2) 个0 和 2**(p-2) 个1\n",
    "        # 由数学归纳法，易得 从1到p位上，各位置有 2**(p-1) 个 1\n",
    "        # 而共有 2**p - 1 个数字\n",
    "        # 将其中 2**(p-1) - 1 个数字，置换为 A = 1\n",
    "        # 最大数字无需置换, 仍为 B = 2**p-1 \n",
    "        # 其余 2**(p-1) -1 个数字，置换为 C = 2**p - 2 = B - 1\n",
    "        # 最终，乘积为 S = A ** T * B ** 1 * C ** T\n",
    "        # 其中 T = 2**(p-1) - 1\n",
    "        # S可化简为 S = B * C ** T = C ** (T+1) + C**T  \n",
    "        c = 2**p - 2 \n",
    "        t = 2**(p-1)  - 1\n",
    "        mod = 10**9+ 7  \n",
    "        c = c%mod  \n",
    "        @lru_cache(None)\n",
    "        def my_pow(p, i):\n",
    "            if i==1:\n",
    "                return p \n",
    "            k, v = divmod(i,2)\n",
    "            q = my_pow(p,k)\n",
    "            if v==1:\n",
    "                rv = (q*q*p)%mod \n",
    "            else:\n",
    "                rv = (q*q)%mod \n",
    "            return rv   \n",
    "        rv = my_pow(c,t+1) + my_pow(c,t)\n",
    "        rv = rv%mod \n",
    "        return rv  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        Mod = int(1e9+7)\n",
    "        return (pow((1 << p) - 2, (1 << (p-1)) - 1, Mod) * ((1 << p) -1)) % Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        mod=10**9+7\n",
    "        return pow(2**p-2,2**(p-1)-1,mod)*(2**p-1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, 10 ** 9 + 7) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        max_num = pow(2, p, MOD) - 1\n",
    "        \n",
    "        x = max_num - 1\n",
    "        time = pow(2, p - 1) - 1\n",
    "\n",
    "        res = max_num % MOD * pow(x, time, MOD) % MOD\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
